package exercises.newcoder.solution;

import exercises.newcoder.util.TreeNode;

/**
 * <a href="https://www.nowcoder.com/practice/512688d2ecf54414826f52df4e4b5693?tpId=202&&tqId=38838&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking">
 * WC129 完全二叉树结点数</a>
 *
 * @author or2
 * @Description 给定一棵完全二叉树的头节点head，返回这棵树的节点个数。如果完全二叉树的节点数为，请实现时间复杂度为O(log^2N)O(log
 * 2 *  N)的解法。
 * @create 2021年09月11日 时间: 11:02
 */
public class NodeNum {

    public int nodeNum(TreeNode head) {
        if (head == null) {
            return 0;
        }
//        记录当前树的总节点数目
        int totalNums = 0;
//        分别计算左右子树最大高度
        int deepLeft = deep(head.left);
        int deepRight = deep(head.right);
//        左子树为满二叉树
        if (deepLeft == deepRight) {
//            计算左子树结点个数
            totalNums += (1 << deepLeft);
//            累加右子树结点个数
            totalNums += nodeNum(head.right);
//        右子树为满二叉树
        } else {
            totalNums += (1 << deepRight);
            totalNums += nodeNum(head.left);
        }

        return totalNums;
    }

    /**
     * 当前树的最大深度
     * @param head 当前树的根节点
     * @return 最大深度
     */
    private int deep(TreeNode head) {
//        最大满二叉树
        int num = 0;
        TreeNode p = head;
        while (p != null) {
            p = p.left;
            num++;
        }

        return num;
    }
}
